package com.yuren.codecrushlearn.Q5300;

import java.util.Collections;
import java.util.List;

/**
 * Created with Intellij IDEA.
 * Description:
 *
 * @author 10204
 * @date 2025-05-23 01:59
 */public class Q5362 {

    /**
     * 贪心算法，先对任务时间数组进行排序，然后遍历数组，计算出每个任务的等待时间，最后将所有任务的等待时间相加即可。
     * 时间复杂度为 O(nlogn)，空间复杂度为 O(1)。
     * 其中，n 为任务数量。
     * 排序的时间复杂度为 O(nlogn)，遍历数组的时间复杂度为 O(n)，因此总时间复杂度为 O(nlogn)。
     * 空间复杂度为 O(1)，因为只需要常数级别的额外空间。
     * @param t
     * @param n
     * @return
     */
    public int findMinWaitingTime(List<Integer> t, int n) {
        Collections.sort(t);

        int total = 0;
        for (int i = 1; i < n; ++i) {
            total += t.get(i - 1) * (n - i);
        }
        return total;
    }
}
